package algorithm.swordoff;

/**
 * 丑数
 *
 * K神思路: dp数组递推
 * 核心在于怎么知道第n个数字是要求的, 递推的大小关系怎么确定
 * 显然丑数只能由前面的丑数 *2 or *3 or *5 得到
 * 刚刚被乘过的丑数显然不可能在下一轮继续被比较,而没被乘过的丑数也不可能越过没被乘过的丑数在比较中
 * 因此分配三个指针分别指向上一轮被 *2 or *3 or *5 的索引
 */

public class SQ49 {

    public int nthUglyNumber(int n) {
        if (n == 0) return 0;
        int[] ans = new int[n + 1];
        ans[1] = 1;
        int lastMulti2 = 1, lastMulti3 = 1, lastMulti5 = 1;

        for (int i = 2; i <= n; i++) {
            int multi2 = ans[lastMulti2] * 2, multi3 = ans[lastMulti3] * 3, multi5 = ans[lastMulti5] * 5;
            ans[i] = Math.min(Math.min(multi2, multi3), multi5);
            // 注意这个地方,如果有多个multi?=ans[i],即多个multi?都是最大值,那么对应的索引都要+1
            // 例子,索引为6的数字是6,此时3*2可以是它,2*3也可以是它,而2对应的索引3和3对应的索引2都要+1
            if (ans[i] == multi2) lastMulti2++;
            if (ans[i] == multi3) lastMulti3++;
            if (ans[i] == multi5) lastMulti5++;
        }
        return ans[n];
    }

    public static void main(String[] args) {
        SQ49 sq49 = new SQ49();
        System.out.println(sq49.nthUglyNumber(10));
    }
}
